import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author CY
 * @date 2022/10/30 17:26
 **/
public class Test1 {
    //    public boolean isPalindromic(String s) {
//        int len = s.length();
//        for (int i = 0; i < len / 2; i++) {
//            if (s.charAt(i) != s.charAt(len - i - 1)) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    // 暴力解法
//    public String longestPalindrome(String s) {
//        String ans = "";
//        int max = 0;
//        int len = s.length();
//        for (int i = 0; i < len; i++) {
//            for (int j = i + 1; j <= len; j++) {
//                String test = s.substring(i, j);
//                if (isPalindromic(test) && test.length() > max) {
//                    ans = s.substring(i, j);
//                    max = Math.max(max, ans.length());
//                }
//            }
//        }
//        return ans;
//    }
    //动态规划解决最长回文子串问题
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] arr = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i == j) {
                    arr[i][j] = true;
                }
            }
        }
        int start = 0;
        int end = 1;
        int maxStart = 0;
        int maxEnd = 0;
        int maxLen = 0;
        for (end=1; end < len; end++) {
            for (start=0; start < end; start++) {
                if (s.charAt(start) == s.charAt(end) && ((end - start < 2 || arr[start + 1][end - 1]))) {
                    arr[start][end] = true;
                    if (maxLen < end - start + 1) {
                        maxStart = start;
                        maxEnd = end;
                        maxLen = Math.max(maxLen, end - start + 1);
                    }
                }

            }
        }
        return s.substring(maxStart, maxEnd+1);
    }

    public static void main(String[] args) {
        Test1 test1 = new Test1();
        System.out.println(test1.longestPalindrome("aba"));
//        Integer[] arr = {5, 3, 435, 6, 57};
//        Arrays.toString(arr);
//        Arrays.sort(arr);
//        Arrays.sort(arr, (o1, o2) -> o2 - o1);
//        List<Integer> list = new ArrayList<Integer>(Arrays.asList(arr));
//        list.add(79);
////        list.forEach(s-> System.out.println(s));
//
//        arr = list.toArray(new Integer[list.size()]);
//        System.out.println(Arrays.toString(arr));

//        System.out.println(Arrays.stream(arr).count());


//        System.out.println(A);
//        for (Integer integer : arr) {
//            System.out.println(integer);
//        }
    }


}
